package com.veal98.bactrack;

import java.util.ArrayList;
import java.util.List;

public class LC93 {

    List<String> res = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        if (s == null || s.length() == 0 || s.length() > 12) {
            return res;
        }

        // 从哪个位置切割（加入逗点）
        int start = 0;
        // 分成几段(IP 地址规定了必须为 4 段)
        int pointNum = 0;
        backtrack(s, start, pointNum);
        return res;
    }

    private void backtrack(String s, int start, int pointNum) {
        // 结束条件
        if (pointNum == 3) {
            // 分为 3 段的时候，判断最后一段是否符合条件，若符合，则将本次分割的结果加入 res
            if (isVaild(s, start, s.length() - 1)) {
                res.add(s);
                return;
            }
        }

        // 遍历选择列表
        for (int i = start; i < s.length(); i++) {
            // 剪枝
            if (!isVaild(s, start, i)) {
                continue;
            } else {
                // 做选择(在 i 的后面加入逗点) substring 左闭右开
                s = s.substring(0, i + 1) + "." + s.substring(i + 1, s.length());
                pointNum ++;
                // 进入下一层解空间树(插入逗点之后下一个子串的起始位置为 i + 2)
                backtrack(s, i + 2, pointNum);
                // 回溯
                s = s.substring(0, i + 1) + s.substring(i + 2, s.length()); // 删除逗点
                pointNum --;
            }
        }

    }

    // 判断是否满足条件（左闭右闭）
    private boolean isVaild(String s, int start, int end) {
        if (start > end) {
            return false;
        }

        // 前导 0
        if (s.charAt(start) == '0' && start != end) {
            return false;
        }

        int sum = 0;
        for (int i = start; i <= end; i++) {
            // 非法字符
            if (s.charAt(i) > '9' || s.charAt(i) < '0') {
                return false;
            }

            sum = sum * 10 + s.charAt(i) - '0';
            if (sum > 255 || sum < 0) {
                return false;
            }
        }

        return true;
    }
}

